Done
好久没打CF，不会打了啊(实际上是变菜了
A.B.C
- A,B签到。
- C题思路正确，写挫了。
D
题意
$2×n$的方格用黑白染色分成$k$个区域的方案数$\mod 998244353$
题解
- 这种计数显然dp解决，赛时想了个dp[i][j]:表示前i行，现在考虑到了第i行第j个，发现不会转移，实际上把考虑行变成考虑列就行了。
- 考虑每一列只有四种状态，每个状态可以由前面一列确定而来。
- dp[i][k][mask]:前i列连通块数量为k当前列状态为mask的方案数。
E
题意
题解
- SA-dp
F
题意
给一个n个点m条边的无向边权图，q次询问(u,v)的最短路
$(u,v,q\le 10^5,m-n\le 20)$
题解
- 随便搞出一颗生成树来
- 非树边的端点不会超过40个，这些直接dij求单源最短路
- 对于每个询问(u,v)，显然有两种方式得到最短路，1.是通过lca， 2.是通过这些非树边的端点得到
G
留坑